1. Field of the Invention
The present invention relates to a floor plan determination apparatus/method for the circuit, such as an LSI (Large Scale Integration) circuit, etc., and a program storage medium used to implement the apparatus, and in particular it relates to the apparatus/method for an LSI block of fixed shape and the medium used to implement such an apparatus.
Along with the recent advancement of circuit technologies, the degree of integration of an LSI (in particular a VLSI) has remarkably improved and the circuit size has also remarkably increased. Along with both the improvement in the degree of integration and the increase of the circuit size, the number of blocks and RAMs (RandomAccessMemory) included in one LSI has also increased. Therefore, if a layout of a floor plan is manually generated, an optimal layout cannot be always obtained and it also takes time. In this way, the development of a technology to enable the acquisition of an optimal floor plan in a small CPU time and to improve the turn around time is demanded.
2. Description of the Related Art
When the layout of an LSI is automatically generated, first, functions of the LSI are divided. Then, a chip area required to implement the respective functions is calculated. Finally, the LSI floor plan is determined by dividing the LSI chip area into a plurality of rectangular areas.
A floor plan optimization method by a slicing tree used in this method is widely known.
In the floor plan by a slicing tree, hierarchical partitioning is repeated and the rectangular shape and location of each LDS block are calculated. This hierarchical structure is expressed by a character string of Polish expression.
For example, if a vertical cutline and a horizontal cutline are expressed as xe2x80x9c*xe2x80x9d and xe2x80x9c+xe2x80x9d, respectively, the floor plan shown in FIG. 1A can be expressed by the following Polish expression, as shown in FIG. 1B.
16+35*2+74+**
The xe2x80x9c*xe2x80x9d and xe2x80x9c+xe2x80x9d are called operators, and figures are called operands.
In the floor plan by a slicing tree, a floor plan is optimized by transforming this Polish expression, which means transforming the tree structure of a slicing tree.
As an optimization algorithm, for example, Simulated Annealing (hereinafter called xe2x80x9cSAxe2x80x9d) is used.
As shown in FIG. 1C, in this SA, the initial solution S0 and initial temperature T0 of Polish expression are set (step ST1), and Polish expression is operated at each set temperature T (step ST8) until the temperature reaches a stipulated termination temperature Tx (steps ST2, ST3 and ST4). In this way, it is assumed that Polish expression is transformed from S to Sxe2x80x2 and the cost of S Cost(S) and cost of Sxe2x80x2 Cost(Sxe2x80x2) at that time are calculated. Then, the following value is calculated (step ST5).
min(1, exe2x88x92[Cost(Sxe2x80x2)xe2x88x92Cost(S)]/T)
If the value is larger than a random real value which is generated between 0 and 1, S is transformed to Sxe2x80x2, and if the value is smaller than the value, S is not transformed (steps ST6 and ST7). This operation is repeated and if the number of repetitions reaches a stipulated number MaxCount, temperature T is reduced toward Tx. In this way, the optimal solution of Polish expression is calculated.
As the transformation operation of Polish expression, exchanging two adjacent operands of Polish expression, or extracting a specific part of Polish expression and making a complement (transforming xe2x80x9c*xe2x80x9d to xe2x80x9c+xe2x80x9d or xe2x80x9c+xe2x80x9d to xe2x80x9c*xe2x80x9d) of an operator included in the art are prepared.
In SA, if Cost(Sxe2x80x2) less than Cost(S), the following inequality holds true.
exe2x88x92[Cost(Sxe2x80x2)xe2x88x92Cost(S)]/T greater than 1
Therefore, the following equation holds true.
min(1, exe2x88x92[Cost(Sxe2x80x2)xe2x88x92Cost(S)]/T)=1
In this way, if the value becomes larger than a random value which is generated between 0 and 1, S is always transformed to Sxe2x80x2. Specifically, if the cost decreases (a high evaluation value is obtained), S is always transformed to Sxe2x80x2.
However, if Cost(Sxe2x80x2) greater than Cost(S), the following expression holds true.
exe2x88x92[Cost(Sxe2x80x2)xe2x88x92Cost(S)]/T=m less than 1
In the above expression, the higher temperature T is, the closer to 1 m is. Therefore, the following inequality holds true.
min(1, exe2x88x92[Cost(Sxe2x80x2)xe2x88x92Cost(S)]/T) less than 1
In this way, some time S is transformed to Sxe2x80x2 and other times S is not transformed to Sxe2x80x2 depending on a random value which is generated between 0 and 1. In this case, the higher the temperature, the higher a possibility that S may be transformed to Sxe2x80x2.
Specifically, in SA, when the value is in the initial state of high temperature, S is sometimes transformed to Sxe2x80x2 even if the cost increases. Therefore, there is a possibility of obtaining a better solution compared with another optimization algorithm, regardless of the initial solution.
In the conventional LSI floor plan by a slicing tree, division is made taking into consideration only the area of each LSI block and the shape. For example, a final cutline is drawn according to the division form specified by Polish expression and depending on the area of each LSI block. Therefore, if an LSI block the shape of which is specified must be laid out, a floor plan in which such an LSI block can be laid out cannot be prepared, which is a problem.
Specifically, a RAM of fixed shape, etc., is sometimes mounted on an LSI chip. In this case, in the conventional LSI floor plan by a slicing tree, if an LSI block of fixed shape, such as a RAM, etc., must be laid out, a floor plan cannot be prepared in such a way that an LSI block can be laid out since the shape of the LSI block is not taken into consideration, which is a problem.
It is an object of the present invention to provide an LSI floor plan determination apparatus for determining an LSI floor plan in such a way that the layout of an LSI block of fixed shape can also designated, a method there of and a program storage medium on which is recorded a program used to implement such an apparatus.
In the first aspect of the present information, the floor plan determination apparatus comprises an execution device, an assignment device and a determination device.
The execution device either inputs or generates the initial solution of layout descriptive information that describes the layout of circuit blocks, which is a circuit floor plan. The assignment device assigns the initial value of a rotation code indicating the orientation of a circuit block to a circuit block of fixed shape described in the layout descriptive information. The determination device determining a circuit floor plan by repeating a process of operating either the layout descriptive information or rotation code on a condition that a circuit block of fixed shape can be laid out, calculating the evaluation value of a floor plan obtained after the operation and judging whether either the layout descriptive information or rotation code should be modified, based on the evaluation value.
In the second aspect of the present invention, the floor plan determination apparatus comprises an execution device, an assignment device and a determination device.
The execution device executes either inputs or generates the initial solution of layout descriptive information that describes the layout of circuit blocks, which is a circuit floor plan omitting circuit blocks of fixed shape. The assignment device assigns the initial value of a circuit block of non-fixed shape, which is a parent block, including the circuit block of fixed shape, to the circuit block of fixed shape. The determination device determines a circuit floor plan by repeating a process of operating either the layout descriptive information or parent block, calculating the evaluation value of a floor plan obtained after the operation and judging whether either the layout descriptive information or rotation code should be modified, based on the evaluation value.
In the third aspect of the present invention, the floor plan determination apparatus comprises an execution device and a determination device.
The execution device either inputs or generates the initial solution of layout descriptive information that describes the layout of circuit blocks, which is a circuit floor plan. The determination device reaches a determination by repeating a process of operating layout descriptive information, merging a circuit block of fixed shape with one or more other circuit blocks if a circuit block of fixed shape cannot be laid out in a floor plan specified by layout descriptive information after the operation, packing the circuit block of fixed shape in an area obtained by the merger, calculating the evaluation value of the floor plan obtained after the packing and judging whether the layout descriptive information should be modified, based on the evaluation value.